package special;

import java.util.*;

class RandomizedSet {
    List<Integer> list = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    final Random r = new Random();

    public RandomizedSet() {

    }
    
    public boolean insert(int val) {
        if (!map.containsKey(val)){
            list.add(val);
            map.put(val, list.size() - 1);
            return true;
        }
        return false;
    }
    
    public boolean remove(int val) {
        if (map.containsKey(val)){
            int index = map.get(val);
            Integer last = list.get(list.size() - 1);
            map.remove(val);
            if (last != val){
                list.set(index, last);
                map.put(last, index);
                list.remove(list.size() - 1);
            }else {
                list.remove(index);
            }
            return true;
        }
        return false;
    }
    
    public int getRandom() {
        int i = r.nextInt(list.size());
        return list.get(i);
    }
}